Теперь можно определить алгоритм Current-Best-Learning, приведенный в листинге 19.1. Обратите внимание на то, что каждый раз при рассмотрении возможности обобщения или уточнения гипотезы необходимо проверять согласованность этих операций с другими примерами, поскольку произвольное увеличение/уменьшение расширения может привести к включению/исключению рассматривавшихся ранее отрицательных/положительных примеров.

Листинг 19.1. Алгоритм обучения по методу поиска текущей наилучшей гипотезы. Он осуществляет поиск совместимой гипотезы и выполняет возврат, если не удается найти какое-либо совместимое уточнение/обобщение

Выше в данном разделе обобщение и уточнение были определены как операции, модифицирующие расширение гипотезы. Теперь необходимо точно определить, как эти операции могут быть реализованы в виде синтаксических операций, которые вносят изменения в потенциальное определение, связанное с гипотезой, чтобы эти операции можно было выполнять с помощью какой-то программы. Прежде чем приступить к решению этой задачи, необходимо отметить, что обобщение и уточнение также представляют собой логические связи между гипотезами. Если гипотеза Η1 с определением d является обобщением гипотезы н2 с определением с2, то должно иметь место следующее выражение:

Поэтому, чтобы сформировать обобщение гипотезы H2, необходимо просто найти определение С1, которое логически следует из С2. Такая задача решается довольно легко. Например, если С2 (х) представляет собой высказывание Al ternate (x) ^ Раtrons (x, Some), то одно из возможных обобщений задается в виде d (x) =Раtrons (x, Some). Такая форма операции обобщения называется удалением условий. Интуитивно ясно, что в результате такой операции формируется более слабое определение и поэтому гипотеза допускает использование более крупного множества положительных примеров. Может быть также предусмотрен целый ряд других операций обобщения, в зависимости от языка, в котором выражаются эти операции. Аналогичным образом, уточнение гипотезы может осуществляться путем введения дополнительных условий в ее потенциальное определение или путем удаления дизъюнктов из какого-то дизъюнктивного определения. Рассмотрим, как могут быть выполнены подобные операции в задаче с рестораном, используя данные, приведенные в табл. 18.1.